Distributed computing systems such as datacenters and other computing systems typically include routers, switches, bridges, and other physical network devices that interconnect a large number of servers, network storage devices, and other types of nodes via wired or wireless network links. The individual nodes can host one or more virtual machines or other types of virtualized components accessible to cloud computing clients. The virtual machines can exchange messages such as emails via virtual networks in accordance with one or more network protocols supported by the physical network devices.